\documentclass {article}
\usepackage [spanish,activeacute] {babel}
\author {Santiago D. Costarelli, Dario G. Uberti}
\title {The Resource-constrained Project Scheduling Problem (RCPSP) : a first approach}
\begin {document}
\maketitle
\section {Introducci\'on}
El Problema de Secuenciaci\'on de Proyectos con Recursos Limitados (RCPSP) es considerado como un problema importante dentro de la secuenciaci\'on con recursos limitados y su utilizaci\'on es muy variada dentro del campo de planificaci\'on de proyectos. El RCPSP consiste en organizar las tareas de determinada actividad sujetas a dos tipos de restricciones. La primera es una relaci\'on de precedencia que impone que algunas actividades deben comenzar luego de que otras hayan concluido. La segunda tiene en cuenta que cada actividad requiere recursos, los cuales son finitos y fijos dada una unidad de tiempo. El objetivo entonces del RCPSP consiste en encontrar la sucesi\'on de actividades de manera que se minimice la longitud del proyecto (makespan).  

El m\'etodo con el cual buscaremos resolver el problema que nos compete es mediante algoritmos geneticos (GA's), llamados as\'i porque se inspiran en la evoluci\'on biol\'ogica y su base gen\'etica. Estos algoritmos hacen evolucionar una poblaci\'on inicial de individuos (posibles soluciones) someti\'endola a acciones aleatorias semejantes a las que act\'uan en la evoluci\'on biol\'ogica (mutaciones y recombinaciones gen\'eticas como cruzas), as\'i como tambi\'en a una selecci\'on de acuerdo con alg\'un criterio, en funci\'on del cual se decide cu\'ales son los individuos m\'as aptos, que sobreviven para luego procrearse, y cu\'ales los menos aptos, que son descartados y su material gen\'etico no prospera en la misma proporci\'on de generaci\'on a generaci\'on como en el caso de los primeros.

Es importante recalcar que, al ser algoritmos del tipo N-P, sus soluciones en general seran del tipo heur\'isticas y dado que el problema es del tipo multiobjetivos, se busca minimizar algun parametro que implicitamente condicione a otro.

\section {M\'etodos}
Basandonos en lo anterior, es fundamental definir una representaci\'on para los individuos de nuestra poblaci\'on. Nuestro cromosoma (individuo) ser\'a denominado proyecto, y estar\'a compuesto por tareas que ser\'ian los genes del mismo. Al inicio un conjunto de $ n $ individuos seran escogidos con sus tareas al azar, previamente verificando que no existan dos tareas iguales asignadas al mismo individuo. Este conjunto ser\'a el que evolucionara, es decir, se le aplicaran operadores de recombinaci\'on para obtener la soluci\'on de nuestro problema.


Los operadores que hemos incluido son en primer lugar el de cruza con $ 2 $ puntos, que consiste en dado dos individuos $ I_{i} $ e $ I_{j} $  con $ i,j \in [0,1..,n-1] $ obtener dos valores al azar $ c_{1},c_{2} \in (0,1..,k-1) $ tal que $ c_{1}<c_{2} $ donde $ k $ es la longitud de cada individuo (en nuestro caso la cantidad de tareas) y luego ir conmutando $ I_{i}(x) $ con $ I_{j}(x) $ $ \forall x \in [c_{1};c_{2}] $. En segundo lugar el de mutaci\'on, que consiste en dado un individuo  $ I_{i} $ efectuar una permutaci\'on de genes (tareas) mediante dos valores al azar, $ m_{1} $ y $ m_{2} $ donde $ m_{1},m_{2} \in (0,1..,k-1) $ tal que $ m_{1} \neq m_{2} $, y luego intercambiar el contenido de  $ I_{i}(m_{1}) $ con el de $ I_{i}(m_{2}) $.

Es importante recalcar que estos operadores solo se aplicaran cuando un valor aleatorio supere un cierto umbral impuesto por el usuario y que adem\'as se propuso un m\'etodo de reparaci\'on de gen al aplicar el operador de cruza. Sea $ I_{i} $ e $ I_{j} $ dos individuos distintos y los valores o puntos de cruza $ c_{1} $ y $ c_{2} $ definidos en el p\'arrafo anterior, antes de efectuar la conmutaci\'on del material se revisa si $ I_{j}(x) $ $ \forall x \in [c_{1};c_{2}]$ se encuentra en $ I_{i}(x) $ $ \forall x \in [0;c_{1}) \cup (c_{2};k-1] $ y viceversa, de ser as\'i no se intercambia esa tarea, de otra forma si. 

Para explicar la metodolog\'ia aplicada a la funci\'on de fitness antes deberemos definir algunos elementos que se tuvieron encuenta. Como se explic\'o al inicio, cada tarea tiene adem\'as de un n\'umero que la identifica p.e. $ j $, su longitud en periodos de tiempo (un periodo es la minima unidad de medida de tiempo), las tareas que requiere que se cumplan antes de ella $ T_{j} $ y los recursos que necesita $ R_{j} $ (donde tanto $ T_{j} $ y $ R_{j} $ son conjuntos con tantos elementos como tareas previas y recursos respectivamente requiera la tarea $ j $).
Tanto al inicio antes del bucle de la evoluci\'on, como al efectuarse las cruzas y las mutaciones, se deber\'a calcular cuan bien cada individuo en particular resuelve nuestro problema, esto sera nuestro \emph {fitness} o \emph {funcion de fitness}. Para esto, dado un individuo $ I $ en particular tendremos en cuenta tres restricciones:

\begin {enumerate}
  \item {Para cada tarea $ j $ del individuo $ I $, tendremos un conjuntos de tareas previas $ T_{j}$ requeridas para su ejecuci\'on, que de no cumplirse incrementar\'an al fitness en un determinado valor. Para esto, dentro del algoritmo se trata a $ T_{j}$ como un vector, luego se toma cada tarea de $ T_{j}$ y se realiza una b\'usqueda dentro del individuo verificando que esta tarea haya sido ejecutada. Conjuntamente se determinan bloques de tareas que pueden ser ejecutadas en paralelo, lo que define al individuo como un conjunto de segmentos, donde no coexisten tareas con relaci\'on de sucesi\'on entre ellas.}
  \item {Se dispone de un vector que contiene los recursos y sus cantidades disponibles, luego se recorre el individuo y se verifica que para cada tarea exista la cantidad de recursos necesarios, de ser as\'i se decrementan los valores del vector de recursos respecto a los requerimientos de la tarea. Este procedimiento actua sobre bloques de tareas paralelas renovando la cantidad de recursos una vez ejecutado el bloque completo. En caso de no satisfacerse las necesidades de recursos necesarios, el fitness es incrementado con la suma de los valores absolutos de las cantidades faltantes (aquellos requerimientos que tengan valor negativo).}
	\item {Se toma como makespan a la suma de las duraciones m\'aximas de las tareas por cada segmento, luego se compara con el makespan deseado y se incrementa al fitness en esta cantidad penalizandolo con un coeficiente $ \alpha $  tal que $ \alpha > 1 $.}
\end {enumerate}

Entonces de lo anterior se deriva, que la b\'usqueda consistir\'a en encontrar el individuo $ I_{w} $ tal que $ f_{I_{w}}=0 $. 

Como se introdujo en el p\'arrafo anterior, el hecho de verificar la ejecuci\'on de las tareas previas requeridas para cada actividad, es la base para la paralelizaci\'on de tareas, que es lo que nos permite minimizar la duraci\'on del proyecto. En el algoritmo la clave esta en conocer a priori una estimaci\'on del valor que deber\'ia tener la duraci\'on del proyecto, entonces de esta forma a medida que el algoritmo encuentre posibles soluciones corroborara que la restriccion del tiempo tambien se cumpla. Esto viene ligado al hecho de que p.e. cuando en una organizaci\'on se compra cierta maquinaria para una tarea espec\'ifica, se sabe que tiempo estimado de producci\'on tiene, lo que resta es buscar la sucesi\'on de tareas que cumplan los requerimientos de precedencia.

El m\'etodo de selecci\'on optado fue el metodo de competencia, en el cual se escogen $ l $ individuos al azar $ I_{i} $ donde $ i \in [0,1,..,l-1] $ (otro parametro que impone el usuario) por cada individuo de la poblaci\'on inicial, cada uno de ellos con su fitness $ f_{I_{i}} $ correspondiente y se elige como ganador al de mayor fitness $ \min_{i \in [0,1,..,l-1]} f_{I_{i}} $. El motivo de la elecci\'on fue porque adem\'as de ser econ\'omico en cuanto a computo p.e. comparado con el de ventana, es mas preciso que el anterior y en trabajos previos nos resulto muy eficiente.

\section {Pruebas}
A continuaci\'on nos propusimos validar el algoritmo utilizando listas clasicas de la libreria PSPLIB (http://129.187.106.231/psplib/), que contienen proyectos creados mediante un programa de los cuales se dispone la soluci\'on \'optima. Como primera instancia resolvimos un problema particular del conjunto J30 como se observa en la siguiente tabla: 

\begin {center}
	\begin{tabular}{|c |c |c |c |}
		\hline
		Tarea & Tareas Previas & Duraci\'on & Recursos \\
		\hline
		1	&	2-3-4 & 0 & 0-0-0-0 \\
		\hline
		2	& 10-11-28 & 2 & 1-2-4-0 \\
		\hline
		3	&	9-15-16 & 5 & 0-5-9-10 \\
		\hline
		4	&	5-6-7 & 6 & 8-10-10-0 \\
		\hline
		5	&	8	& 4 & 8-3-0-8 \\
		\hline
		6	& 18-27 & 2	& 3-1-8-5 \\
		\hline
		7	& 14-18 & 9	& 5-0-5-10 \\
		\hline
		8	& 12-13-19 & 9	& 4-0-0-3  \\	
		\hline
		9	& 10 & 4	& 8-0-8-10  \\			
		\hline
		10 & 22 & 8	& 0-0-0-5	 \\		
		\hline
		11 & 25 & 7	& 1-6-6-6	 \\		
		\hline
		12 & 30 & 10 & 2-10-3-8	\\		
		\hline
		13 & 20 & 1	& 10-8-2-8 \\			
		\hline
		14 & 31 & 1	& 1-3-6-1 \\ 			
		\hline
		15 & 21-24 & 1	& 4-0-9-9 \\ 		
		\hline
		16 & 17-27-30 & 5	& 0-9-6-9 \\ 	
		\hline
		17 & 18 & 2	& 4-3-9-10 \\ 			
		\hline
		18 & 21 & 5	& 0-10-9-0 \\			
		\hline
		19 & 29 & 5	& 2-7-9-0 \\ 			
		\hline
		20 & 23 & 9	& 0-5-4-1 \\ 			
		\hline
		21 & 26 & 10 & 0-8-0-8 \\ 			
		\hline
		22 & 23 & 1	& 9-0-0-6 \\ 			
		\hline
		23 & 26 & 5	& 4-8-3-8 \\ 			
		\hline
		24 & 25 & 4	& 5-7-3-5 \\			
		\hline
		25 & 26-27-30 & 10 & 9-0-0-1 \\	
		\hline
		26 & 29 & 5	& 1-8-0-7 \\			
		\hline
		27 & 31 & 9	& 7-3-4-7 \\ 			
		\hline
		28 & 31 & 10 & 7-0-0-3 \\			
		\hline
		29 & 32 & 2	& 1-3-0-10 \\	
		\hline
		30 & 32 & 10	& 4-0-3-7 \\			
		\hline
		31 & 32 & 3	& 0-4-5-1 \\			
		\hline
		32 &  & 0	& 0-0-0-0 \\ 				
		\hline
	\end{tabular}
\end {center}

Los resultados utilizando 20 individuos con una tasa de cruza del $ 80\% $, una tasa de mutaci\'on del $ 30\% $ y tomando 5 individuos en la competencia son los siguientes:

\begin {center}
	\begin{tabular}{|c |c |c |c |}
		\hline
		Tiempo requerido (makespan) & Tiempo total de computo [seg] \\
		\hline
		82	&	4.2 \\		
		\hline
		101	&	18.32 \\		
		\hline
		82	&	7.17 \\		
		\hline
		93	&	5.39 \\		
		\hline
		69 & 15.63 \\	
		\hline
		82	&	4.2 \\		
		\hline
	\end{tabular}
\end {center}

Donde se observa la discrepancia de makespan producto de los problemas que tuvimos en agregar esta condicion al codigo. Otra cosa que se observa son los tiempo de resoluci\'on, donde a veces parece iniciar cerca de soluciones factibles y esto ayuda a la velocidad de convergencia. 

\section {Conclusiones}
Al comparar los resultados obtenidos con los brindados por la libreria, vemos que nuestro algoritmo resuelve el problema de una manera sub\'optima y esto se debe a que tenemos dificultades al incluir la restriccion 3 de la que hablamos anteriormente (makespan) la cual solo tuvimos en cuenta para obtener la duraci\'on final del proyecto, pero no para la optimizaci\'on. Adem\'as, no hemos utilizado m\'as m\'etodos de optimizaci\'on entre los cuales podemos destacar el bit de \emph{modo}, el cual consiste en interpretar la lista de actividades segun este bit, aplicando los operadores de recombinaci\'on hacia adelante o atras obteniendo dos individuos distintos, tomando luego aquel de mejor fitness lo que se ha demostrado en [1] y [2] que ayuda a la velocidad de convergencia del m\'etodo.

\section {Referencias}
[1] A Robust Genetic Algorithm for Resource Allocation in Project Scheduling - J. ALCARAZ and C. MAROTO - Annals of Operations Research 102, 83–109, 2001.

[2] Genetic Algorithms for the Resource-Constrained Project Scheduling Problem - Javier Alcaraz Soria y Concepción Maroto Álvarez - Boletín de Estadística e Investigación Operativa Vol. 25, No. 1, Febrero 2009, pp. 22-31s.

[3] Genetic Algorithm for the Resource-Constrained Project Scheduling Problem Using Encoding with Scheduling Mode - Vu Thien Can, Jacques A. Ferland, Nguyen Huu Anh - December 6, 2004.

[4] Hartmann S., y Kolisch R. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: an update. Eur J Opl Res, 174, 23-37. 

\end {document}

